/**
 * 链表相加(二)
 * 描述
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
 * 要求：
 * 空间复杂度O(n)，
 * 时间复杂度 O(n)
 *
 * 例如：
 * 链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 */

/**
 * 这里的加法和之前的一样, 只不过是要先把它反转过来再使用
 * 后面我们用一个新的链表来接收加法的结果
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {

        // 反转链表
        ListNode cur1 = reverseList(head1);
        ListNode cur2 = reverseList(head2);

        // res 来操作加法
        ListNode res = new ListNode(0);

        // newHead 来记录头结点的位置
        ListNode newHead = res;

        // 进位标志
        int tmp = 0;

        // 加法运算
        while (cur1 != null || cur2 != null || tmp != 0) {

            if (cur1 != null) {
                tmp += cur1.val;
                cur1 = cur1.next;
            }

            if (cur2 != null) {
                tmp += cur2.val;
                cur2 = cur2.next;
            }

            ListNode next = new ListNode(tmp % 10);

            tmp /= 10;

            // 这里记得更新 res 的位置
            res.next = next;
            res = next;
        }

        // 返回反转后的节点
        return reverseList(newHead.next);
    }

    // 反转链表
    public ListNode reverseList(ListNode head) {

        // 为 null 是特殊情况, next 为 null 是递归出口
        if (head == null || head.next == null) {
            return head;
        }

        // 先递归找最底层
        ListNode newHead = reverseList(head.next);

        // 反转逻辑
        head.next.next = head;
        head.next = null;

        // 最后返回新的头节点
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}